home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / string.arc / _STR2PAT.C < prev    next >
Encoding:
C/C++ Source or Header  |  1984-12-31  |  1.5 KB  |  42 lines
  1. /*  File   : _str2pat.c
  2.     Author : Richard A. O'Keefe.
  3.     Updated: 2 June 1984
  4.     Defines: _pat_lim, _pat_vec[], _str2pat()
  5.  
  6.     Searching in this package is done by an algorithm due  to  R.  Nigel
  7.     Hospool,  described  in  Software  Practice & Experience 1980, p505.
  8.     Elsewhere I have a version of it which does  exact  case  or  either
  9.     case  match,  word  more or literal mode, forwards or backwards, and
  10.     will look for the Nth instance.  For most applications that  is  too
  11.     much  and  a  simple  exact  case forward search will do.  Hospool's
  12.     algorithm is a simplification of  the  Boyer-Moore  algorithm  which
  13.     doesn't  guarantee linear time, but in practice is very good indeed.
  14.  
  15.     _str2pat(pat) builds a search table for the string pat.  As usual in
  16.     this pacakge, if pat == NullS, the table is not changed and the last
  17.     search string is re-used.  To support  this,  _str2pat  returns  the
  18.     actual search string.
  19. */
  20.  
  21. #include "strings.h"
  22. #include "_str2pat.h"
  23.  
  24. int    _pat_lim;
  25. int    _pat_vec[_AlphabetSize];
  26. static    _char_    *oldPat = "";
  27.  
  28.  
  29. _char_ *_str2pat(pat)
  30.     register _char_ *pat;
  31.     {
  32.     register int L, i;
  33.  
  34.     if (pat == NullS) pat = oldPat; else oldPat = pat;
  35.     for (L = 0; *pat++; L++) ;
  36.     for (i = _AlphabetSize; --i >= 0; _pat_vec[i] = L) ;
  37.     for (pat = oldPat, i = L; --i > 0; _pat_vec[*pat++] = i) ;
  38.     _pat_lim = --L;
  39.     return oldPat;
  40.     }
  41.